1. Field of the Invention
The present invention is related to the calculating method of a type of key equation polynomials which is applied in the decoding process of an error correction code, and the corresponding key equation polynomial generator. The key equation polynomials especially comprise an errata locator polynomial and an errata evaluator polynomial.
2. Description of the Prior Art
In the present era of the world of computer networks, people always transfer data by the computer and the internet in their lives or jobs. However, errors in data transferring will unavoidably arise after the data has been transferred from the transmitting location to the destination through a variety of different mediums. The error can be caused by the noise from the transferring paths and (or) transfer medium itself. Therefore, the transferred data will be different from the received data. There is a lot of methods and techniques being developed to detect and correct the received data. Among these, one of the methods is to generate a codeword for the signal part (transferred data) and the parity part (the message to implement the error correction). In this paper, codeword is obtained from encoding the original data, the codeword is the message contained N signals, wherein the signal part is represented by K signals, and the parity part is represented by N−K signals.
As in well-known error correction codes, the BCH (Bose-Chaudhuri-Hocquenghen Codes) and the RS (Reed-Solomon Codes) are the most commonly used Block Codes. The theorems of the BCH Codes and the RS Codes are described in detail in E. R. Berlekamp, Algoebraic Coding Theory, McGraw-Hill, New York, 1968 and S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Applications, Prentice-Hall, Englewood Cliffs, N.J., 1983 respectively.
A (N, K) BCH, or RS Code contains K message signals and N encoded signals, wherein the signals of the BCH Codes belong to the collection of GF (q), and the signals of the RS Codes belong to the collection of GF (qm). A binary (N, K) BCH Code is capable of correcting t error signals under the condition of N=2m−1 and N−K≦mt. However, a (N, K) RS Code is capable of correcting t error signals and p erasure signals under the condition of t=└(N−K−ρ)/2┘. For the binary BCH Codes, an error signal can be corrected easily by discovering the position of the error signal. For the RS Codes, an error signal can be corrected by discovering the position and error value of the error signal. Furthermore, the definition of an erasure signal in the RS Codes is an error with the known error position; in other words, an error signal can be corrected by discovering the error value.
Referring to FIG. 1, FIG. 1 is the flowchart of decoding architecture of the RS decoder. If the error signal is going to be corrected by using the normal architecture of RS decoder, then the method is summarized into four steps as below in FIG. 1A: (1) calculate the Syndrome 10 by the received codeword, (2) calculate the error locator polynomial and error evaluator polynomial 12, (3) calculate the position of the error 14, and (4) calculate the error value 16. If both the error and the erasure signal are going to be corrected, then the above mentioned four steps are amended as below in FIG. 1B: (1) calculate the Forney Syndrome 18 by the received codeword and erasure position, (2) calculate the errata locator polynomial and errata evaluator polynomial 20, (3) calculate the position 22 of the error, and (4) calculate the correct value 24 of the error and erasure value. The steps in FIG. 1C are: (1) calculate the Syndrome 26 by the received codeword, and calculate the erasure polynomial 28 by the erasure position, (2) calculate the errata locator polynomial and errata evaluator polynomial 30, (3) calculate the position 32 of the error, and (4) calculate the correct value 34 of the error and erasure value.
In the prior art, the key equation polynomial calculation method is referred to the U.S. Pat. No. 6,119,262 which implements the Inverseless Berlekamp-Massey algorithm, and the U.S. Pat. No. 6,286,123 which implements the Berlekamp-Massey algorithm; the U.S. Pat. No. 5,889,793 which implements the Euclidean Algorithm. The above mentioned prior art usually updates only one coefficient or one decomposed data of the coefficient calculation in one single clock cycle. The systems in the prior art, like an optical reproducing system, reads and transmits data in slower speed, yet there will not be problem or delay when the speed of the decoding of data is not required to be too fast. However, the speed of systems has been continuously increased, and the speed of reading and transmitting of data has been greatly increased also. To accommodate such transmitting speed, the prior art usually increases the clock cycle frequency of data decoding, so as to complete decoding within the required time. However, this method of increasing clock cycle frequency to solve the problem also requires a great deal of increase in system power consumption. Therefore, this is not an acceptable solution for those who cannot afford such increase in system power consumption.